package 笔试;

public class 归并排序 {
    private static void merge(int[] a,int[] aux,int low,int mid,int high){
        for(int i=low;i<=high;i++)
            aux[i]=a[i];
        //a的元素都拷贝到aux中
        int i=low,j=mid+1;
        //i,j分别是左右两部分第一个元素的下标1
        for(int k=low;k<=high;k++){
            if(i>mid)//左半部分
                a[k]=aux[j++];
            else if(j>high)
                //右半部分
                a[k]=aux[i++];
            else if(aux[j]<aux[i])
                //下标j的元素更小
                a[k]=aux[j++];
            else a[k]=aux[i++];
            //反之
        }
    }
    private static void sort(int[] a,int[] aux,int low,int high){
        if(high==low)return ;
        //下标相同则无需处理
        else if(high==low+1){
            //当low和high的下标相差1,则问题简化为两个数的排序,也就是简单的交换
            if(a[low]>a[high]){
                //当low下标的数字大于high下标的数字,交换两个数
                int temp=a[low];
                a[low]=a[high];
                a[high]=temp;
            }
            return;
        }
        //否则将问题分解
        int mid=low+(high-low)/2;
        sort(a,aux,low,mid);
        //左半边有序
        sort(a,aux,mid+1,high);
        //右半边有序
        merge(a,aux,low,mid,high);
    }
    public static void sort(int[] a){
        int[] aux=new int[a.length];
        //为临时数组分配空间
        sort(a,aux,0,a.length-1);
    }

    public static void main(String[] args) {
        int[] a = new int[]{8,0,7,9,5,1,2,4,3};
        sort(a);
        for (int j : a) {
            System.out.println(j);
        }
    }
}
